package Leetcode;

import base.ListNode;

/**
 * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 */
public class 力扣148_排序链表 {

    public static void main(String[] args) {
        ListNode a1 = new ListNode(3);
        ListNode a2 = new ListNode(5);
        ListNode a3 = new ListNode(1);
        ListNode a4 = new ListNode(4);
        ListNode a5 = new ListNode(2);
        a1.next = a2;
        a2.next = a3;
        a3.next = a4;
        a4.next = a5;

        ListNode listNode = sortList1(a1);
        System.out.println(listNode);
    }

    static ListNode sortList1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 快慢指针拆分链表
        ListNode fast = head, slow = head, slowPre = null;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slowPre = slow;     // 注意保存slow的前驱节点
            slow = slow.next;
        }
        slowPre.next = null;    // 一定从slow的前面断开链表 否则此处为null  比如: 5->1 到这里后 head=5 slow=1  执行后 h1=5->1 h2=null 死循环
        ListNode h1List = sortList1(head);
        ListNode h2List = sortList1(slow);
        return mergeList(h1List, h2List);
    }

    // 合并链表
    static ListNode mergeList(ListNode h1, ListNode h2) {
        if (h1 == null) {
            return h2;
        }
        if (h2 == null) {
            return h1;
        }
        // 注意临时节点的应用
        ListNode dummyHead = new ListNode(-1);
        ListNode tmp = dummyHead;
        while (h1 != null && h2 != null) {
            if (h1.val < h2.val) {
                tmp = tmp.next = h1;
                h1 = h1.next;
            } else {
                tmp = tmp.next = h2;
                h2 = h2.next;
            }
        }
        tmp.next = h1 == null ? h2 : h1;
        return dummyHead.next;
    }

}
